var exist = function (board, word) {
  let visited = [];
  let row = board.length;
  let col = board[0].length;
  let now = 0;
  for (let i = 0; i < row; i++) {
    visited[i] = [];
  }
  for (let x = 0; x < row; x++) {
    for (let y = 0; y < col; y++) {
      if (search(visited, now, x, y)) return true;
    }
  }
  function search(visited, now, x, y) {
    if (now == word.length) return true;
    let hasPath = false;
    if (
      x >= 0 &&
      x < row &&
      y >= 0 &&
      y < col &&
      board[x][y] == word[now] &&
      !visited[x][y]
    ) {
      now++;
      visited[x][y] = true;
      hasPath =
        search(visited, now, x + 1, y) ||
        search(visited, now, x - 1, y) ||
        search(visited, now, x, y + 1) ||
        search(visited, now, x, y - 1);
      if (!hasPath) {
        now--;
        visited[x][y] = false;
      }
    }
    return hasPath;
  }
  return false;
};

var exist = function (board, word) {
  // 越界处理
  board[-1] = [];
  board.push([]);

  // 寻找首个字母
  for (let x = 0; x < board.length; x++) {
    for (let y = 0; y < board[0].length; y++) {
      if (word[0] == board[x][y] && backtrack(x, y, 0)) return true;
    }
  }

  function backtrack(x, y, i) {
    let temp = board[x][y];
    // 标记该元素已使用
    board[x][y] = false;

    if (board[x][y + 1] == word[i + 1] && backtrack(x, y + 1, i + 1))
      return true;
    if (board[x][y - 1] == word[i + 1] && backtrack(x, y - 1, i + 1))
      return true;
    if (board[x + 1][y] == word[i + 1] && backtrack(x + 1, y, i + 1))
      return true;
    if (board[x - 1][y] == word[i + 1] && backtrack(x - 1, y, i + 1))
      return true;

    // 回溯
    board[x][y] = temp;
  }
};
